﻿// 0919train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <queue>

using namespace std;

/*
对于一个连续正整数组成的序列，可以将其拼接成一个字符串，再将字符串里的部分字符打乱顺序
如序列8 9 10 11 12，拼接成的字符串为89101112，打乱一部分字符后得到90811211，
原来的正整数10就被拆成了0和1

现给定一个按如上规则得到的打乱字符的字符串，
请将其还原成连续正整数序列，并输出序列中最小的数字

输入描述
输入一行，为打乱字符的字符串和正整数序列的长度，两者间用空格分隔，
字符串长度不超过200，正整数不超过1000，保证输入可以还原成唯一序列

输出描述
输出一个数字，为序列中最小的数字

输入
19801211 5
输出
8

还原出的序列为 8 9 10 11 12，故输出 8
 */
class Solution01
{
public:
    Solution01(string&str, int length)
    {
        vector<int>target_v;
        for (auto&ch:str)
        {
            target_v.push_back(ch - '0');
        }
        sort(target_v.begin(), target_v.end());

        //正整数不超过1000
        int start = 0;
        while (start+ length<=1000)
        {
            vector<int>curr_v;
            for (int i=start;i<start+length; i++)
            {
                string num_str = to_string(i);
                for (auto&ch:num_str)
                {
                    curr_v.push_back(ch - '0');
                }
            }
            sort(curr_v.begin(), curr_v.end());

            if (curr_v==target_v)
            {
                break;
            }
            start++;
        }

        cout << start;
        //Solution01
    }
};

/*
 商人经营一家店铺，有 number 种商品，由于仓库限制每件商品的最大持有数量是 item[index]
 每种商品的价格在每天是 item_price[item_index][day]
 通过对商品的买进和卖出获取利润，请给出商人在 days 天内能获取到的最大的利润
注： 同一件商品可以反复买进和卖出

输入
3     // 输入商品的数量 number
3     // 输入商人售货天数 days
4 5 6 // 输入仓库限制每件商品的最大持有数量是 item[index]
1 2 3 // 输入第一件商品每天的价格
4 3 2 // 输入第二件商品每天的价格
1 5 3 // 输入第三件商品每天的价格

输出
32     // 输出商人在这段时间内的最大利润

 */
class Solution02
{
public:
    Solution02(vector<int>&para_v, vector<vector<int>>&prices)
    {
        //d天 k件商品 0没有 1持有
        //dp[d][k][0] = max(dp[d-1][k][0], dp[d-1][k][1]+prices[k][d])
        //dp[d][k][1] = max(dp[d-1][k][1], dp[d-1][k][0]-prices[k][d])
        if (prices.empty()) return;
        vector<int>status(2);
        int total_amount = prices.size();//商品数量
        vector<vector<int>>single_item(total_amount, status);
        int total_day = prices[0].size();
        vector<vector<vector<int>>>dynamic_v(total_day, single_item);

        //初始化第0天
        int day_0 = 0;
        for (int k=0; k<total_amount; k++)
        {
            //未拥有 k
            dynamic_v[day_0][k][0] = 0;
            //拥有 k 买入
            dynamic_v[day_0][k][1] = -prices[k][0];
        }

        for (int d=1; d<total_day; d++)
        {
            for (int k=0; k<total_amount; k++)
            {
                //d-1未拥有
                int prev_0 = dynamic_v[d - 1][k][0];
                //d-1拥有
                int prev_1 = dynamic_v[d - 1][k][1];
                dynamic_v[d][k][0] = max(prev_0, prev_1 + prices[k][d]);

                dynamic_v[d][k][1] = max(prev_1, prev_0 - prices[k][d]);
                //for total_amount
            }
	        //for d
        }

        int result = 0;
        for (int k=0; k<total_amount; k++)
        {
            int curr_p = para_v[k];
            result += curr_p * dynamic_v[total_day - 1][k][0];
        }
        cout << result;
	    //Solution02
    }
};


/*
部门组织绿岛骑行团建活动。租用公共双人自行车，每辆自行车最多坐两人，最大载重M
给出部门每个人的体重，请问最少需要租用多少双人自行车

输入描述
第一行两个数字m、n，分别代表自行车限重，部门总人数
第二行，n个数字，代表每个人的体重，体重都小于等于自行车限重m

输出描述
最小需要的双人自行车数量

输入
3 4
3 2 2 1
输出
3
 */
class Solution03
{
public:
    Solution03(vector<int>&num_vec, int limit)
    {
        sort(num_vec.begin(), num_vec.end());

        int left = 0, right = num_vec.size() - 1;

        int result = 0;
        while (left<=right)
        {
            if (left==right)
            {
                result += 1;
                break;
            }
            if (num_vec[left]+num_vec[right]<=limit)
            {
                result += 1;
                left++;
                right--;
            }
            else
            {
                result += 1;
                right--;
            }
            //while
        }
        cout << result;
	    //Solution03
    }
};


/*
近些年来，我国防沙治沙取得显著成果
某沙漠新种植N棵胡杨（编号1-N），排成一排
一个月后，有M棵胡杨未能成活
现可补种胡杨K棵，请问如何补种（只能补种，不能新种) ,可以得到最多的连续胡杨树?

输入描述
N：总种植数量 1<=N<=10^5
M：未成活胡杨数量 1<=M<=N
M个空格分隔的数，按编号从小到大排列
K：最多可以补种的数量0 <= K <= M

输出描述
最多的连续胡杨棵树

输入
5
2
2 4
1
输出
3
补种胡杨2或4，可以得到连续的胡杨[1, 2, 3]或[3, 4, 5]

输入
10
3
2 4 7
1
输出
6
补种胡杨7，可以得到连续的胡杨[5, 6, 7, 8, 9, 10]
 */
class Solution04
{
public:
    Solution04(int total, unordered_set<int>&fail_set, int target_count)
    {
        //不定滑窗 未成功1 成功0 1的数量等于target_count的最长序列
        //编号1-N

        vector<int>exec_vec(total + 1);
        int v_size = exec_vec.size();
        for (int i=1; i<v_size; i++)
        {
            if (fail_set.count(i)>0)
            {
                exec_vec[i] = 1;
            }
            else
            {
                exec_vec[i] = 0;
            }
	        //for
        }

        int max_length = 0;
        int curr_count = 0;
        int left = 1;
        for (int right=1; right<v_size; right++)
        {
            if (exec_vec[right]==1)
            {
                curr_count++;
            }

            while (curr_count>target_count)
            {
                if (exec_vec[left]==1)
                {
                    curr_count--;
                }
                left++;
	            //while
            }

            if (curr_count==target_count)
            {
                max_length = max(right - left + 1, max_length);

            }

	        //for---
        }

        cout << max_length;
	    //Solution04
    }
};


/*
歌手准备从 A 城去 B 城参加演出
1. 按照合同，他必须在 T 天内赶到
2. 歌手途径 N 座城市
3. 歌手不能往回走
4. 每两座城市之间需要的天数都可以提前获知
5. 歌手在每座城市都可以在路边卖唱赚钱
经过调研，歌手提前获知了每座城市卖唱的收入预期
如果在一座城市第一天卖唱可以赚 M，后续每天的收入会减少 D (第二天赚的钱是 M-D，第三天是 M-2D…)
如果收入减到 0 就不会再少了
6. 歌手到达后的第二天才能开始卖唱。如果今天卖过唱，第二天才能出发
问贪心的歌手最多可以赚多少钱？

输入描述
第一行两个数字 T 和 N，中间用空格隔开，T 代表总天数；
N 代表路上经过 N 座城市;

第二行 N+1 个数字，中间用空格隔开，代表每两座城市之间耗费的时间，其总和<=T
接下来 N 行，每行两个数字 M 和 D，中间用空格隔开。代表每个城市的收入预期

输出描述
一个数字。代表歌手最多可以赚多少钱。以回车结束

输入
10 2
1 1 2
120 20
90 10
输出
540

总共 10 天，路上经过 2 座城市。
路上共花 1+1+2=4 天。
剩余 6 天最好的计划是在第一座城市待 3 天，在第二座城市待 3 天。
在第一座城市赚的钱：120 + 100 + 80 = 300
在第二座城市赚的钱：90 + 80 + 70 = 240
共 300 +240 = 540
 */
class Solution05
{
public:
    struct Node
    {
        int val, diff;
    	Node() = default;
        Node(int val, int diff) :val(val), diff(diff) {};
        bool operator<(const Node&other)const
        {
            return val < other.val;
        }
    };
    Solution05(int total, vector<int>&cost_v, vector<vector<int>>&choose_v)
    {
        int cost_day = 0;
        for (auto&d:cost_v)
        {
            cost_day += d;
        }

        priority_queue<Node>p_queue;

        for (auto&item:choose_v)
        {
            Node node(item[0], item[1]);
            p_queue.push(node);
        }

        int remain_day = total - cost_day;
        int result = 0;
        while (!p_queue.empty()&&remain_day>0)
        {
            Node top_node = p_queue.top();
            p_queue.pop();

            result += top_node.val;
            remain_day -= 1;
            top_node.val = top_node.val - top_node.diff;

            if (top_node.val>0)
            {
                p_queue.push(top_node);
            }
	        //while
        }

        cout << result;
	    //Solution05
    }
};

int main()
{
	{
        int total, v_size;
        cin >> total >> v_size;

        vector<int>cost_v(v_size + 1);
        for (int i=0; i<v_size+1; i++)
        {
            cin >> cost_v[i];
        }

        vector<vector<int>>choose_v;
        for (int i=0; i<v_size; i++)
        {
            vector<int>item(2);
            cin >> item[0] >> item[1];
            choose_v.push_back(item);
        }

        Solution05 solu(total, cost_v, choose_v);

        return 0;
	}
	{
        int total, v_size;
        cin >> total >> v_size;

        unordered_set<int>fail_set;
        for (int i=0; i<v_size; i++)
        {
            int num;
            cin >> num;
            fail_set.insert(num);
        }

        int target_count;
        cin >> target_count;

        Solution04 solu(total, fail_set, target_count);

        return 0;
	}
	{
        int limit, v_size;
        cin >> limit >> v_size;

        vector<int>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        Solution03 solu(num_vec, limit);
        return 0;
	}
	{
        int total_amount, total_day;
        cin >> total_amount >> total_day;

        vector<int>para_v(total_amount);
        for (int k=0; k<total_amount; k++)
        {
            cin >> para_v[k];
        }

        vector<vector<int>>prices(total_amount, vector<int>(total_day));
        for (int k=0; k<total_amount; k++)
        {
            for (int d=0; d<total_day; d++)
            {
                cin >> prices[k][d];
            }
        }

        Solution02 solu(para_v, prices);

        return 0;
	}
    //19801211 5
    string str;
    cin >> str;
    int length;
    cin >> length;

    Solution01 solu(str, length);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
